package weekMatch.one_350;

import java.util.Arrays;

public class LeeCode_04 {
    public static void main(String[] args) {
//        System.out.println(paintWalls(new int[]{1, 2, 3, 2}, new int[]{1, 2, 3, 2}));
        System.out.println(paintWalls(new int[]{2,3,4,2}, new int[]{1,1,1,1}));
    }
    private static int paintWalls(int[] cost, int[] time) {
        int n = cost.length;
        int[][] dp = new int[n][n * 2 + 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }
        return dfs(dp, cost, time, n - 1, n);
    }
    private static int dfs(int[][] dp, int[] cost, int[] time, int i, int j){
        int n = cost.length;
        if (i < j - n)
            return 0;
        if (i < 0)
            return 0x3f3f3f3f;
        if (dp[i][j] != - 1)
            return dp[i][j];
        dp[i][j] = Math.min(dfs(dp, cost, time, i - 1, j + time[i]) + cost[i], dfs(dp, cost, time, i - 1, j - 1));
        return dp[i][j];
    }
}